'''
Created on Jul 19, 2011

@author: anupams
'''

from com.anupam.graphs.GraphsAnupam import SampleGraphObject

class DepthFirstSearch(object):
  """
    Performs depth first search on the graph
  """

  def __init__(self, graphDict, nodes):
    """
    Default constructor of the class.
    
    Args:
      graphDict : Adjucancy list of the graph
      nodes : graph node objects @see{ColoredGraphNode}
    """

    self.graphDict = graphDict
    self.nodes = nodes
    self.counter = 0
    self.firstVisitTime = {}
    self.lastVisitTime = {}
    pass

  def __printProcessedNode(self, nodeName):
    """
      Prints information about a processed node.
    """

    print 'Information for the node : ' + nodeName
    print 'first visit time : ' + str(self.firstVisitTime[nodeName])
    print 'last  visit time : ' + str(self.lastVisitTime[nodeName]) + '\n'

  def __doDFS(self, nodeName):
    """
    Perfroms a depth first search on the provided adjucancy list of the graph.
      Args :
        nodeName : Starting node that is to be treated as graph root
    """

    nodeObj = self.nodes[nodeName]
    nodeObj.color = 'grey'
    self.counter = self.counter + 1
    self.firstVisitTime[nodeName] = self.counter
    adjucancyList = self.graphDict[nodeName]
    copyOfAdjucancyList = list(adjucancyList)

    while len(copyOfAdjucancyList):
      childNodeName = copyOfAdjucancyList.pop(0)
      childNodeObj = self.nodes[childNodeName]
      if childNodeObj.color == 'white':
        self.__doDFS(childNodeName)
      else :
        continue
    nodeObj.color = 'black'

    self.counter = self.counter + 1
    self.lastVisitTime[nodeName] = self.counter
    self.__printProcessedNode(nodeName)

  def checkUnprocessedNodes(self):
    """
      Iterates over the nodes of the graph and checks if any 
      node is white in color. It uses that node as the start of 
      of new forest rooted at that node.
    """

    for key in self.nodes:
      nodeObj = self.nodes[key]
      if nodeObj.color == 'white':
        print '#####################################################'
        print '##     Start of a forest rooted at node : ' + key
        print '#####################################################' + '\n'
        self.__doDFS(key)
      else:
        continue


if __name__ == '__main__':
  directedGraphSample = SampleGraphObject()
  graphDict = directedGraphSample.directedGraphSample()
  traverse = DepthFirstSearch(graphDict, directedGraphSample.nodes)
  traverse.checkUnprocessedNodes()
